﻿#include "stdafx.h"
#include "FindDisappearedNumbers.h"

using namespace std;

namespace algorithm {
vector<int> CFindDisappearedNumbers::Find(vector<int>& nums)
{
    vector<int> res;
    int flag = 1<<30;
    int size = nums.size();
    for (int i = 0; i < size; i++) {
        int num = nums[i] & (~flag);
        nums[num - 1] |= flag;
    }
    for (int i = 0; i < size; i++) {
        if ((nums[i] & flag) != flag) {
            res.push_back(i+1);
        }
        else
        {
            // 还原值
            int num = nums[i] & (~flag);
            nums[i] = num;
        }
    }
    return res;
}
std::vector<int> CFindDisappearedNumbers::Find_v1(std::vector<int>& nums)
{
    vector<int> res;
    bitset<100000 + 1> bs;
    int size = nums.size();
    for (int i = 0; i < size; i++) {
        bs.set(nums[i]);
    }
    for (int i = 1; i <= size; i++) {
        if (!bs.test(i)) {
            res.push_back(i);
        }
    }
    return res;
}
}
